#ifndef MSORT_HPP
#define MSORT_HPP
#include <vector>
namespace myh{
    #define THRESHOLD 16
    void Sort(std::vector<int>& arr) {
        size_t n=arr.size(),curr_size,left_start;
        if(n<=THRESHOLD) {
            for(size_t i=1;i<n;i++) {
                int key=arr[i],j=i-1;
                while(j>=1&&arr[j]>key) {
                    arr[j+1]=arr[j];
                    j--;
                }
                arr[j+1]=key;
            }
            return;
        }
        for(curr_size=1;curr_size<n;curr_size*=2) {
            for (left_start=0;left_start<n;left_start+=2*curr_size) {
                int mid=left_start+curr_size-1;
                int right=std::min(left_start+2*curr_size-1,n-1);
                if(mid<right){
                    int n1=mid-left_start+1,n2=right-mid;
                    int rightStart=mid+1,rightEnd=right;
                    int* L=&arr[left_start],*R=&arr[rightStart];
                    int i=0,j=0,k=left_start;
                    while (i<n1&&j<n2) {
                        if(*(L+i)<=*(R+j)) arr[k++]=*(L + i++);
                        else arr[k++]=*(R+j++);
                    }
                    while(i<n1) arr[k++]=*(L+i++);
                    while(j<n2) arr[k++]=*(R+j++);
                }
            }
        }
    }
}
#endif